/**
 * Copyright (c) 2012-2013 Nokia Corporation. All rights reserved.
 * Nokia and Nokia Connecting People are registered trademarks of Nokia Corporation.
 * Oracle and Java are trademarks or registered trademarks of Oracle and/or its
 * affiliates. Other product and company names mentioned herein may be trademarks
 * or trade names of their respective owners.
 * See LICENSE.TXT for license information.
 */

package com.nokia.example.amaze.model;

import java.util.Random;

/**
 * The model of the maze.
 */
public class Maze {
    // Constants
    private final static int UP = 0;
    private final static int DOWN = 1;
    private final static int LEFT = 2;
    private final static int RIGHT = 3;
    private final static int MAX_SIZE = 31;
    
    // Members
    private long[] _maze = null; // Maze rows are encoded as bits in a long field
    private final float _sideLength;
    private final float _height;

    // Utility variables
    private final float _origin;
    private float _spaceBetweenPlanes = 0f;
    
    // Store the location on X of the start and end
    private int _startX = -1;
    private int _endX = -1;

    /**
     * Constructor.
     * @param corridorCount
     * @param mazeSideLength
     * @param mazeHeight
     */
    public Maze(final int corridorCount,
                final float mazeSideLength,
                final float mazeHeight)
    {
        if (corridorCount > MAX_SIZE) {
            throw new IllegalArgumentException("Maze is too big!");
        }
    
        _sideLength = mazeSideLength;
        _height = mazeHeight;
        _origin = -_sideLength / 2;
    }
    
    /** 
     * @return The maze height.
     */
    public final float height() {
        return _height;
    }

    /** 
     * @return The maze origin.
     */
    public final float origin() {
        return _origin;
    }
    
    /** 
     * @return The space between planes.
     */
    public final float spaceBetweenPlanes() {
        return _spaceBetweenPlanes;
    }
    
    /** 
     * @return The maze content as an array.
     */
    public final long[] array() {
        return _maze;
    }
    
    /**
     * @return The X coordinate of the start position in the maze.
     */
    public final int startX() {
        return _startX;
    }
    
    /**
     * @return The X coordinate of the goal in the maze.
     */
    public final int goalX() {
        return _endX;
    }
    
    /**
     * Resolves and returns the start position. 
     * @return The start position.
     */ 
    public float[] startPosition() {
        float[] position = new float[3];
        position[0] = _origin + _startX * _spaceBetweenPlanes;
        position[1] = _height / 2; // Not used, hopefully
        position[2] = _origin + _spaceBetweenPlanes;
        return position;
    }

    /**
     * Checks if the given position (x, z) is near enough of the end (goal)
     * position of the maze. The "near enough" is determined by the given
     * tolerance.
     * @param x
     * @param z
     * @param tolerance
     * @return
     */
    public final boolean isAtTheEnd(final float x,
                                    final float z,
                                    final float tolerance)
    {
        // Use linear distances
        return Math.abs(x - (_origin + _endX * _spaceBetweenPlanes))
                < tolerance
                && Math.abs(z + _origin) < tolerance;
    }

    /**
     * Creates a new random maze.
     * @param mazeSize The size of the maze array to create.
     */ 
    public void createNew(int mazeSize) {
        _startX = -1;
        _endX = -1;
        Random random = new Random();
        int totalSize = mazeSize * 2 + 1;
        _maze = new long[totalSize];
        
        for (int i = 0; i < _maze.length; i++) {
            _maze[i] = -1;
        }
        
        int backtrack[] = new int[mazeSize * mazeSize];
        int backtrackIndex = 0;        
        int x = 1;
        int y = 1;

        // Traverse the maze finding unconnected spots
        while (true) {
            _maze[x] &= ~(0x1 << y);
            int directions[] = new int[4];
            int availableSpaces = 0;
            
            if (y - 2 > 0 && (_maze[x] & (0x1 << (y - 2))) != 0) {
                directions[availableSpaces++] = UP;
            }
            
            if (y + 2 < totalSize && (_maze[x] & (0x1 << (y + 2))) != 0) {
                directions[availableSpaces++] = DOWN;
            }
      
            if (x + 2 < totalSize && (_maze[x + 2] & (0x1 << y)) != 0) {
                directions[availableSpaces++] = LEFT;
            }
      
            if (x - 2 > 0 && (_maze[x - 2] & (0x1 << y)) != 0) {
                directions[availableSpaces++] = RIGHT;
            }

            if (availableSpaces > 0) {
                int chosenDirection =
                        directions[(random.nextInt() >>> 1) % availableSpaces];
                backtrack[backtrackIndex++] = chosenDirection;
        
                if (chosenDirection == UP) {
                    _maze[x] &= ~(0x1 << (y - 1));
                    y -= 2;
                }
                else if (chosenDirection == DOWN) {
                    _maze[x] &= ~(0x1 << (y + 1));
                    y += 2;
                }
                else if (chosenDirection == LEFT) {
                    _maze[x + 1] &= ~(0x1 << y);
                    x += 2;
                }
                else if (chosenDirection == RIGHT) {
                    _maze[x - 1] &= ~(0x1 << y);
                    x -= 2;
                }
            }
            else { // If nothing is not visited in the neigborhood backtrack
                if (backtrackIndex == 0) {
                    // end of algorithm
                    break;
                }
                
                backtrackIndex--;
        
                if (backtrack[backtrackIndex] == UP) {
                    y += 2;
                }
                else if (backtrack[backtrackIndex] == DOWN) {
                    y -= 2;
                }
                else if (backtrack[backtrackIndex] == LEFT) {
                    x -= 2;
                }
                else if (backtrack[backtrackIndex] == RIGHT) {
                    x += 2;
                }
            }
        }

        // Find start and end points
        while (true) {
            int pos = (random.nextInt() >>> 1) % totalSize;
            
            if (_startX < 0 && (_maze[1] & (0x1 << pos)) == 0) {
                _startX = pos;
                //_maze[0] &= ~(0x1 << pos); // Make a hole to the wall
            }
            
            if (_endX < 0 && (_maze[_maze.length - 2] & (0x1 << pos)) == 0) {
                _endX = pos;
                _maze[_maze.length - 1] &= ~(0x1 << pos); // Make a hole to the wall
            }
      
            if (_endX >= 0 && _startX >= 0) {
                break;
            }
        }
        
        _spaceBetweenPlanes = _sideLength / (_maze.length - 1);
    }
    
    /**
     * Releases the resources but keeps the meta information such as the start
     * and the end of the maze last created.
     */
    public void clear() {
        _maze = null;
    }
}
